import entity.TreeNode;

import java.util.LinkedList;

public class SumOfLeftLeaves {
    /*
    * 404. 左叶子之和
    * 给定二叉树的根节点 root ，返回所有左叶子之和。
    * */
    public static void main(String[] args){

    }

    int sum = 0;
    // 我的想法：递归，遇到左叶子记录一下就好
    public int mySolution(TreeNode root){
        if(root == null)
            return 0;
        traversal(root);
        return sum;
    }
    private boolean traversal(TreeNode root){
        if(root.left == null && root.right == null){
            // 叶子节点，返回true
            return true;
        }

        if(root.left != null){
            if(traversal(root.left))
                sum += root.left.val;
        }
        if(root.right != null)
            traversal(root.right);

        return false;
    }

    // 迭代法
    // 比递归的空间开销还要大诶
    public int mySolution2(TreeNode root){
        int res = 0;
        if(root == null)
            return res;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        while (!stack.isEmpty()){
            root = stack.pollLast();
            if(root.right != null)
                stack.add(root.right);
            if(root.left != null){
                if(root.left.left == null && root.left.right == null)
                    res += root.left.val;
                else
                    stack.add(root.left);
            }
        }
        return res;
    }
}
